package com.ljy.my_study.动态规划.编辑距离;

import java.util.Scanner;

/**
 * @author James
 * @date 2018年6月15日
 */
public class TestMain {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(true) {
        String aStr = in.nextLine();
        String bStr = in.nextLine();
        int aLen = aStr.length();
        int bLen = bStr.length();
        int[][] dp = new int[aLen + 1][bLen + 1];
        for (int i = 0; i < aLen + 1; i++) dp[i][0] = i;
        for (int i = 0; i < bLen + 1; i++) dp[0][i] = i;
        for (int i = 1; i < aLen + 1; i++) {
            for (int j = 1; j < bLen + 1; j++) {
            	System.out.println("aStr ("+(i-1)+"):"+aStr.charAt(i - 1));
            	System.out.println("bStr ("+(j-1)+"):"+bStr.charAt(j - 1));
            	System.out.println();
                if (aStr.charAt(i - 1) == bStr.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    System.out.println();
                }	
            }    
            for(int m=0;m<dp.length;m++) {
            	for(int n=0;n<dp[m].length;n++) {
            		System.out.print(dp[m][n]+"	 ");
            	}
            	System.out.println();
            }
            System.out.println();
        }    
        System.out.println(dp[aLen][bLen]);
		}
	}
}
